package seqlist;

import java.util.Arrays;

/**
 * 基于数组的线性表—顺序表【动态数组：DynamicArray】
 */
public class DynamicArray {
    //存储元素还是在数组中存储，只是套了一层类，从类访问就不用管数组长度固定问题
    private int[] data;//定义整型数组
    private int size;//当前动态数组中实际存储元素个数
    public DynamicArray(){//构造方法
        data=new int[10];//data初始化，已知默认开辟10个长度大小
    }
    public DynamicArray(int capacity){
        data=new int[capacity];
    }

    /**
     * 1.在数组的尾部插入
     * @param val 待插入的新元素值
     */
    public void addLast(int val){
        //先判断当前数组是否已满
        if(size==data.length){
            //当前数组已满，需要进行扩容操作grow()【扩容是私有方法】
            grow();
        }
        //执行尾插
        data[size]=val;
        size++;
    }

    /**
     * 2.头插
     * @param val
     */
    public void addFirst(int val){//最后一个位置开始向后移动一个单位，否则会覆盖原先元素
        if(size== data.length){
            grow();
        }
        for (int i = size-1; i >=0 ; i--) {
            data[i+1]=data[i];
        }
        //此时data[0]空出
        data[0]=val;
        size++;
    }

    /**
     * 3.中间位置插入
     * @param val
     * @param index
     */
    public void addIndex(int val,int index){//先给数组扩容在执行合法性判断，否则数组满的情况下插入元素时index>size，插不了
        if(size== data.length){
            grow();
        }
        //判断合法性
        if(index<0||index>size){
            System.err.println("add index illegal");
            return;
        }

//        if(index==0)addFirst(val);
//        else if(index==size)addLast(val);//可以省略，头插尾插也可以当作中间插入
        else{//将index位置空出
            for (int i = size-1; i >=index ; i--) {
                data[i+1]=data[i];
            }
            data[index]=val;
            size++;
        }
    }

    /**
     * 4.在数组中查找val对应的索引下标
     * @param val
     * @return 返回下标
     */
    public int getByValue(int val){
        //遍历数组
        for (int i = 0; i < size; i++) {
            if(data[i]==val){
                return i;
            }
        }
        return -1;
    }

    /**
     * 5.查看当前数组中是否存在val
     * @param val
     * @return
     */
    public boolean contains(int val){
        //遍历
        for (int i = 0; i < size; i++) {
            if(data[i]==val){
                return true;
            }
        }
        return false;
    }

    /**
     * 6.根据索引取得相应位置元素
     * @param index
     * @return 返回元素值val
     */
    public int get(int index){
        //判断index合法性
        if(index<0||index>=size){
            System.err.println("get index iillegal");
            return -1;
        }
        return data[index];
    }

    /**
     * 7.将指定元素修改为newValue，返回修改前的元素值
     * @param index
     * @param newVal
     * @return
     */
    public int set(int index,int newVal){
        if(index<0||index>=size){
            System.err.println("set index illegal");
            return -1;
        }
        int oldVal=data[index];
        data[index]=newVal;
        return oldVal;
    }

    /**
     *8. 删除指定索引位置的元素//index+1的元素通过循环依次前移
     * @param index
     */
    public void removeIndex(int index){
        if(index<0||index>=size){
            System.err.println("remove index illegal!");
            return;
        }
        for (int i = index; i <size-1 ; i++) {//因为取data[i+1]了，i应该<size-1否则会有越界问题
            data[i]=data[i+1];
        }
        size--;
        data[size]=0;//最后那个位置置零【虽然也不会访问到了，但是可以这样写，更严谨】
    }
    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }

    /**
     * 9.删除数组中第一个值为val的元素
     * @param val
     */
    public void removeValueOnce(int val){
        for (int i = 0; i < size; i++) {
            if(data[i]==val){
                removeIndex(i);
                return;
            }
        }
        System.out.println("val不存在");
    }

    /**
     * 10.删除数组中所有值为val的元素
     * @param val
     */
    public void removeValAll(int val){
        for (int i = 0; i < size; i++) {
            while(i!=size&&data[i]==val){//注意这里的while以及i!=size【防止越界，i不能等于size】
                removeIndex(i);
            }
        }
    }
    /**
     * 遍历打印数组,向外部返回字符串
     * @return 向外部返回一个字符串
     */
    public String toString(){
        String ret="[";
        for (int i = 0; i < size; i++) {//不能小于data.length,data.length可能有空，小于size就好
            ret+=data[i];
            if(i!=size-1){
                ret+=",";
            }
        }
        ret+="]";
        return ret;
    }
    /**
     * 数组扩容操作
     */
    private void grow() {
        //data=Arrays.copyOf(data,data.length<<1);//传入原数组名称和新数组长度【<<1：扩容为原来的1倍】；返回扩容后的新数组
        //分开写
        int[] newData=Arrays.copyOf(data,data.length<<1);//传入原数组名称和新数组长度【<<1：扩容为原来的1倍】；返回扩容后的新数组
        this.data=newData;//类中的data指向扩容后的新数组
    }

}
